In 1992, Bartholdi, Tovey, and Trick opened the study of control attacks onelections---attempts to improve the election outcome by such actions asadding/deleting candidates or voters. That work has led to many results on howalgorithms can be used to find attacks on elections and howcomplexity-theoretic hardness results can be used as shields against attacks.However, all the work in this line has assumed that the attacker employs just asingle type of attack. In this paper, we model and study the case in which theattacker launches a multipronged (i.e., multimode) attack. We do so to morerealistically capture the richness of real-life settings. For example, anattacker might simultaneously try to suppress some voters, attract new votersinto the election, and introduce a spoiler candidate. Our model provides aunified framework for such varied attacks, and by constructing polynomial-timemultiprong attack algorithms we prove that for various election systems evensuch concerted, flexible attacks can be perfectly planned in deterministicpolynomial time.
展开▼